//
//  FindMagicIndex.swift
//  LeetCodeSummary
//
//  Created by WangYonghe on 2020/7/31.
//  Copyright © 2020 WangYonghe. All rights reserved.
//  面试题 08.03. 魔术索引

import UIKit

/*
 面试题 08.03. 魔术索引
 魔术索引。 在数组A[0...n-1]中，有所谓的魔术索引，满足条件A[i] = i。给定一个有序整数数组，编写一种方法找出魔术索引，若有的话，在数组A中找出一个魔术索引，如果没有，则返回-1。若有多个魔术索引，返回索引值最小的一个。

 示例1:

  输入：nums = [0, 2, 3, 4, 5]
  输出：0
  说明: 0下标的元素为0
 示例2:

  输入：nums = [1, 1, 1]
  输出：1
 说明:

 nums长度在[1, 1000000]之间
 此题为原书中的 Follow-up，即数组中可能包含重复元素的版本
*/

class FindMagicIndex: NSObject {
    
    //暴力解法  耗时172ms
    func findMagicIndex(_ nums: [Int]) -> Int {

        for i in 0 ..< nums.count{
            if nums[i] == i{
                return i
            }
            
        }
        return -1
    }
    
    //跳跃查找  耗时164ms
    func findMagicIndex2(_ nums: [Int]) -> Int {
        
        var i = 0
        while i < nums.count {
    
            //有些多此一举...
//            if nums[i] < 0{
//                i += 1
//                continue
//            }
    
            if nums[i] == i{
                return i
            }
        
            if nums[i] > i{
                i = nums[i]
            }else{
                i += 1
            }
        }
        
        return -1
    }
    
    
    //官解 二分法 耗时168ms
    func findMagicIndex3(_ nums: [Int]) -> Int {
        
        return self.helper(0, nums.count-1, nums)
    }
    
    func helper(_ left: Int, _ right: Int, _ nums: [Int]) -> Int{
        if left > right {
            return -1
        }
        
        let left = left
        let right = right
        //let mid = left+(right-left)/2+1
        let mid = left+(right-left)/2
        
        let leftAnswei = self.helper(left, mid-1, nums)
        if leftAnswei != -1{
            return leftAnswei
        }else if nums[mid] == mid{
            return mid
        }
        
        return self.helper(mid+1, right, nums)
    }
    
}
